public class Test03 {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null || head.next.next == null) return ;
        // 1. 找到链表的中间节点
        ListNode slow = head, fast = head;
        while( fast != null  && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //2. 反转后半部分的链表
        ListNode dummy = new ListNode();
        ListNode cur = slow.next;
        slow.next = null;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = dummy.next;
            dummy.next = cur;
            cur = curNext;
        }
        //3. 交替合并两个链表
        ListNode cur1 = head, cur2 = dummy.next;
        ListNode newHead = new ListNode(), tail = newHead;
        while(cur1 != null){
            tail.next = cur1;
            tail = cur1;
            cur1 = cur1.next;
            if(cur2 != null){
                tail.next = cur2;
                tail = cur2;
                cur2 = cur2.next;
            }
        }
        return ;
    }
}
